//
// Created by Administrator on 2021/4/15.
//

/*
给出一棵二叉树，其上每个结点的值都是0或1。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
 例如，如果路径为0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数01101，也就是13。

对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。题目数据保证答案是一个 32 位 整数。


示例 1：


输入：root = [1,0,1,0,1,0,1]
输出：22
解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
示例 2：

输入：root = [0]
输出：0
示例 3：

输入：root = [1]
输出：1
示例 4：

输入：root = [1,1]
输出：3


提示：

树中的结点数介于 1 和 1000 之间。
Node.val 为 0 或 1 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-root-to-leaf-binary-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;

struct TreeNode {
    int val; // 节点值
    TreeNode *left; // 左子节点
    TreeNode *right; // 右子节点

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};

class Solution {
private:
    int sumVal = 0;
public:
    int sumRootToLeaf(TreeNode *root) {
        dfs(root, 0);
        return sumVal;
    }

    void dfs(TreeNode *root, int x) {
        if (!root) return;
        int curSum = x * 2 + root->val;
        if ((!root->left) and (!root->right)) {
            // 叶节点
            this->sumVal += curSum;
        }
        dfs(root->left, curSum);
        dfs(root->right, curSum);
    }
};

int main() {
    auto t7 = TreeNode(1);
    auto t6 = TreeNode(0);
    auto t5 = TreeNode(1);
    auto t4 = TreeNode(0);
    auto t3 = TreeNode(1, &t6, &t7);
    auto t2 = TreeNode(0, &t4, &t5);
    auto t1 = TreeNode(1, &t2, &t3);
    Solution sol;
    cout << sol.sumRootToLeaf(&t1);
    return 0;
}